package offer.offer01;

/**
 * 注意常用的 && 和 || 都是短路操作。
 * 别人的想法: 这里不用一个count数组来表示进入过, 而是把进入过的char改成一个别的东西, 比如'\0'(空格不能在word中存在),
 * 出来的时候还会改回来所以也不影响, 判断的时候如果进入过, 就一定不和当前char相等, 不用多去判断, 同时节省空间。
 */
public class S12矩阵中的路径 {
    /**
     * 99, 回溯遍历。可以看到这个矩阵并不大。用另一个矩阵记录是否进入。只有四个方向, 还好。
     */
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0) return false;
        if(word == null || word.length() == 0) return true;

        char[] wordChar = word.toCharArray();
        char[][] count = new char[board.length][board[0].length];
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                // 当第一个char符合的时候, 调用函数判断周围是否存在后续char
                if(board[i][j] == wordChar[0] && existHelp(board, i, j, count, wordChar, 1))
                    return true;
            }
        }
        return false;

    }
    // 判断row, col位置周围是否有当前需要的char
    public boolean existHelp(char[][] board, int row, int col, char[][] count, char[] wordChar, int curPosi){
        if(curPosi == wordChar.length) return true; // word的所有位置都匹配到了
        count[row][col] = 1;
        boolean flag1 = false;
        if(row - 1 >= 0 && board[row - 1][col] == wordChar[curPosi] && count[row - 1][col] == 0)
            flag1 = existHelp(board, row - 1, col, count, wordChar, curPosi + 1);
        // 本来每个flag都没有配置下面这四行的, 但是这样后面的用例会超时, 所以加了这些, 不太体面。
        if(flag1 == true){
            count[row][col] = 0;
            return true;
        }
        boolean flag2 = false;
        if(col + 1 < count[0].length && board[row][col + 1] == wordChar[curPosi] && count[row][col + 1] == 0)
            flag2 = existHelp(board, row, col + 1, count, wordChar, curPosi + 1);
        if(flag2 == true){
            count[row][col] = 0;
            return true;
        }
        boolean flag3 = false;
        if(row + 1 < count.length && board[row + 1][col] == wordChar[curPosi] && count[row + 1][col] == 0)
            flag3 = existHelp(board, row + 1, col, count, wordChar, curPosi + 1);
        if(flag3 == true){
            count[row][col] = 0;
            return true;
        }
        boolean flag4 = false;
        if(col - 1 >= 0 && board[row][col - 1] == wordChar[curPosi] && count[row][col - 1] == 0)
            flag2 = existHelp(board, row, col - 1, count, wordChar, curPosi + 1);
        if(flag4 == true){
            count[row][col] = 0;
            return true;
        }
        count[row][col] = 0;
        return flag1 || flag2 || flag3 || flag4;
    }

    /**
     * 66, 主要把help里的对flag1~4的判断修改到一起了, 用短路或应该是同样的效果, 但是时间慢了一点, 不知为何, 问题不大。
     */
    public boolean exist2(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0) return false;
        if(word == null || word.length() == 0) return true;

        char[] wordChar = word.toCharArray();
        char[][] count = new char[board.length][board[0].length];
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                // 这里和上面只有唯一一点不同就是curPosi从0开始。
                if(board[i][j] == wordChar[0] && existHelp2(board, i, j, count, wordChar, 0))
                    return true;
            }
        }
        return false;

    }
    // 判断row, col位置周围是否有当前需要的char
    public boolean existHelp2(char[][] board, int row, int col, char[][] count, char[] wordChar, int curPosi){
        //System.out.println("" + row + " " + col + " " + wordChar[curPosi]);
        if(curPosi == wordChar.length) return true; // word的所有位置都匹配到了
        // 把是否符合条件的判断移到了前面。
        if(row >= board.length || row < 0 || col >= board[0].length || col < 0
                || board[row][col] != wordChar[curPosi] || count[row][col] == 1) return false;
        count[row][col] = 1;
        boolean flag = existHelp(board, row - 1, col, count, wordChar, curPosi + 1) ||
                existHelp(board, row, col + 1, count, wordChar, curPosi + 1) ||
                existHelp(board, row + 1, col, count, wordChar, curPosi + 1) ||
                existHelp(board, row, col - 1, count, wordChar, curPosi + 1);
        count[row][col] = 0;
        return flag;
    }
}
